﻿#pragma once
#include "Index.h"

class IReverseInteger
{
public:
	/**
	 * 整数反转.
	 * https://leetcode.cn/problems/reverse-integer/
	 *
	 * 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
	 * 如果反转后整数超过 32 位的有符号整数的范围 [−2^31,  2^31 − 1] ，就返回 0。
     * 假设环境不允许存储 64 位整数（有符号或无符号）。
	 */
	virtual int reverse(int x) = 0;
};


class ReverseInteger
{
public:
	class Solution:IReverseInteger
	{
	public:
		int reverse(int x) override
		{
			const bool is_negative = x < 0;
			short high = 0;
			int low = 0;

			//提取x的每个位数的数字
			std::queue<char> q;
			while (std::abs(x) != 0)
			{
				q.push(std::abs(x % 10));
				x /= 10;
			}

			//去除栈顶的0，直到遇到不为0的元素
			while (!q.empty() && q.front() == 0)
				q.pop();

			//高低区构建反序的数字
			for (char i = 0; !q.empty(); ++i, q.pop())
			{
				high *= 10;
				low *= 10;
				low += q.front();

				if (low > LOW)
				{
					high += low >> 16;
					low &= 0x0000ffff;
				}
				if (isOutside(high, low, is_negative))
					return 0;
			}
			return (is_negative ? -1 : 1) * ((high << 16) + low);
		}
	private:
		inline bool isOutside(short hight, int low, bool is_negative)
		{
			if (!is_negative)
				return !(hight <= HIGH && low <= LOW);
			else
				return !(hight <= HIGH && low <= LOW + 1);
		}
	private:
		static const int HIGH = (INT_MAX & 0xffff0000) >> 16;
		static const int LOW = INT_MAX & 0x0000ffff;
	};
};

//#ifdef DEV_TEST
//#include <gtest/gtest.h>
//TEST(ReverseIntTest, reverse)
//{
//	ReverseInteger::Solution s;
//
//	std::cout << s.reverse(1534236469) << std::endl;
//	std::cout << s.reverse(1534236402) << std::endl;
//	std::cout << s.reverse(-1534236402) << std::endl;
//	std::cout << s.reverse(-1534640200) << std::endl;
//}
//#endif